import java.nio.ByteBuffer;

import redis.clients.jedis.Jedis;
import redis.clients.jedis.Pipeline;
import redis.clients.util.MurmurHash;

public class BloomFilter {
	// 误差最小公式 ln2*m/n=k .
	static final int hashCount = 4;// hash函数的个数
	static final int MAX_OFF_SET = 536870911;// 最长的bit位536870911
	private String keySpace;// 用于[keySpace]的BloomFilter
	private Jedis jedis;
	
	/*****
	 * 
	 * @param keySpace
	 */
	public BloomFilter(String keySpace) {
		this.keySpace = keySpace;
		jedis  = new Jedis("127.0.0.1",6379);		
	}

	

	/*****
	 * 放入key
	 * 
	 * @param key
	 */
	public void insert(String key) {
		Pipeline pipeline = jedis.pipelined();
		int[] offsets = getHashBuckets(key);
		for (int offset : offsets) {
			pipeline.setbit(keySpace, offset, true);
		}		
		pipeline.sync();
	}

	/****
	 * 清空BloomFilter
	 * 
	 * @param key
	 */
	public void clear(String key) {
		jedis.set(keySpace, "AA");
	}

	/*****
	 * key是否已存在
	 * 
	 * @param key
	 * @return
	 */
	public boolean include(String key) {
		int[] offsets = getHashBuckets(key);
		for (int offset : offsets) {
			if (jedis.getbit(keySpace, offset) == false)
				return false;
		}
		return true;
	}

	/*****
	 * 删除存在的key
	 * 
	 * @param key
	 */
	public void delete(String key) {
		int[] offsets = getHashBuckets(key);
		Pipeline pipeline = jedis.pipelined();
		for (int offset : offsets) {
			pipeline.setbit(keySpace, offset, false);
		}
		pipeline.sync();
	}

	private int[] getHashBuckets(String key) {
		return BloomFilter.getHashBuckets(ByteBuffer.wrap(key.getBytes()),
				hashCount, MAX_OFF_SET);
	}

	static int[] getHashBuckets(ByteBuffer b, int hashCount, int max) {
		int[] result = new int[hashCount];
		int hash1 = MurmurHash.hash(b.array(), b.position(), b.remaining(), 0);
		int hash2 = MurmurHash.hash(b.array(), b.position(), b.remaining(),
				hash1);
		for (int i = 0; i < hashCount; ++i) {
			result[i] = (int) (Math.abs((hash1 + i * hash2) % max));
		}
		return result;
	}

	public void setJedis(Jedis jedis) {
		this.jedis = jedis;
	}
	
	public static void main(String[] args) {
		String keySpace = "";
		BloomFilter bloomFilter = new BloomFilter(keySpace);
		long tagTime = System.currentTimeMillis();
		for (int i = 1; i < 1000000000; i++) {
			if (i % 100000 == 0)
				System.out.println(i);		
			bloomFilter.insert(i+"");
	
		}
		
		System.out.println((System.currentTimeMillis()-tagTime));
		tagTime = System.currentTimeMillis();
		int count = 0;
		for (int i = 0; i < 100000; i++) {
			if(bloomFilter.include(i+""))
				count++;			
		}
		System.out.println((System.currentTimeMillis()-tagTime)+" "+ count);
		
	}

}